package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class ConstructStringFromBinaryTree {

	//方法一：我写的，递归法
	public String tree2str(TreeNode root) {
		return dfs(root).toString();
	}

	private StringBuilder dfs(TreeNode node) {
		StringBuilder sb = new StringBuilder();
		if (node == null)
			return sb;

		sb.append(node.val);

		if (node.left != null && node.right == null) {
			sb.append("(");
			sb.append(dfs(node.left));
			sb.append(")");
		} else if (node.right != null) {
			sb.append("(");
			sb.append(dfs(node.left));
			sb.append(")(");
			sb.append(dfs(node.right));
			sb.append(")");
		}
		return sb;
	}

	//方法二，别人写的，递归法
	public String tree2str2(TreeNode t) {
		StringBuilder sb = new StringBuilder();
		preorder(t, sb);
		return sb.toString();
	}

	private void preorder(TreeNode root, StringBuilder sb) {
		if (root == null) {
			return;
		}
		sb.append(root.val);
		if (root.left != null) {
			sb.append("(");
			preorder(root.left, sb);
			sb.append(")");
		}
		if (root.right != null) {
			if (root.left == null) {
				sb.append("()");
			}
			sb.append("(");
			preorder(root.right, sb);
			sb.append(")");
		}
	}
}
